package com.hjy.backend.dataManager.pageIndex;

import com.hjy.backend.dataManager.pageCache.PageCache;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 页面索引，缓存了每一页的空闲空间。用于在上层模块进行插入操作时，
 * 能够快速找到一个合适空间的页面，而无需从磁盘或者缓存中检查每一个页面的信息。
 * <p>
 * JyDB 用一个比较粗略的算法实现了页面索引，将一页的空间划分成了 40 个区间。在启动时，就会遍历所有的页面信息，获取页面的空闲空间，安排到这 40 个区间中。
 * <p>
 * insert 在请求一个页时，会首先将所需的空间向上取整，映射到某一个区间，随后取出这个区间的任何一页，都可以满足需求。
 */
public class PageIndex {
    // 将一页划成40个区间
    private static final int INTERVALS_NO = 40;
    private static final int THRESHOLD = PageCache.PAGE_SIZE / INTERVALS_NO; // 8K / 40 = 204

    private Lock lock;
    private List<PageInfo>[] lists; // 每个区间存储的数据, 有 40 项

    @SuppressWarnings("unchecked")
    public PageIndex() {
        lock = new ReentrantLock();
        lists = new List[INTERVALS_NO + 1];
        for (int i = 0; i < INTERVALS_NO + 1; i++) {
            lists[i] = new ArrayList<>();
        }
    }

    /**
     * 让PageIndex管理最新添加的一个数据页(初始化页面索引文件)
     * <p>
     * 每个数据页根据剩余空间的大小, 被安排进不同的 list,由 PageInfo 维护
     *
     * @param pageNumber 页面号
     * @param freeSpace  剩余空间
     */
    public void add(int pageNumber, int freeSpace) {
        lock.lock();
        try {
            // 获取对应的区间号
            int number = freeSpace / THRESHOLD;
            lists[number].add(new PageInfo(pageNumber, freeSpace));
        } finally {
            lock.unlock();
        }
    }

    /**
     * 根据需要的空间大小, 选择适合的数据页
     *
     * @param spaceSize
     * @return
     */
    public PageInfo select(int spaceSize) {
        lock.lock();
        try {
            // 获取区间号
            int sectionId = spaceSize / THRESHOLD;
            if (sectionId < INTERVALS_NO) sectionId++;
            while (sectionId <= INTERVALS_NO) {
                if (lists[sectionId].size() == 0) {
                    // 序号越高, 剩余空间越大
                    sectionId++;
                    continue;
                }
                return lists[sectionId].remove(0);
            }
            return null;
        } finally {
            lock.unlock();
        }

    }
}
